package club.xiaojiawei.queueandstack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/8/22 9:15 PM
 * @question 71. 简化路径
 * @description 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
 * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
 * 请注意，返回的 规范路径 必须遵循下述格式：
 * 始终以斜杠 '/' 开头。
 * 两个目录名之间必须只有一个斜杠 '/' 。
 * 最后一个目录名（如果存在）不能 以 '/' 结尾。
 * 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
 * 返回简化后得到的 规范路径
 */
public class SimplifyPath71 {

    public static void main(String[] args) {
        String path = "/a/./b/../../c/";
        String result = simplifyPath(path);
        System.out.println(result);
    }

    /**
     * 双指针（指向同一个数组）
     * @param path
     * @return
     */
    public static String simplifyPath(String path) {
        String[] split = path.split("/");
        int index = 0;
        for (String s : split) {
            if (s.equals("..")){
                if (index > 0){
                    index--;
                }
            }else if (!s.equals(".") && !s.isEmpty()){
                index++;
                split[index] = s;
            }
        }
        if (index == 0){
            return "/";
        }
        StringBuilder result = new StringBuilder();
        for (int i = 1; i < index + 1; i++){
            result.append("/");
            result.append(split[i]);
        }
        return result.toString();
    }

    /**
     * 双指针（指向同一个数组）
     * @param path
     * @return
     */
    public static String simplifyPath4(String path) {
        String[] split = path.split("/");
        int index = 0;
        for (String s : split) {
            if (s.equals("..")){
                if (index > 0){
                    index--;
                }
            }else if (!s.equals(".") && !s.isEmpty()){
                index++;
                split[index] = "/" + s;
            }
        }
        if (index == 0){
            return "/";
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i < index + 1; i++){
            builder.append(split[i]);
        }
        return builder.toString();
    }

    /**
     * 官方-栈
     * @param path
     * @return
     */
    public static String simplifyPath2(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<String>();
        for (String name : names) {
            if ("..".equals(name)) {
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else if (name.length() > 0 && !".".equals(name)) {
                stack.offerLast(name);
            }
        }
        if (stack.isEmpty()) {
            return "/";
        } else {
            StringBuilder ans = new StringBuilder();
            while (!stack.isEmpty()) {
                ans.append('/');
                ans.append(stack.pollFirst());
            }
            return ans.toString();
        }
    }

    /**
     * 民间-双指针（指向两个数组）
     * @param path
     * @return
     */
    public static String simplifyPath3(String path) {
        char[] origin = (path + '/').toCharArray();
        char[] stack = new char[path.length() + 1];
        int idx = 0;
        stack[idx++] = '/';
        for (int i = 0, c = 0; i < origin.length; i++) {
            if (origin[i] != '/') {
                c++;
                stack[idx++] = origin[i];
                continue;
            }
            if (stack[idx - 1] == '/') {
                continue;
            }
            if (stack[idx - 1] != '.' || (c == 2 && stack[idx - 2] != '.') || c > 2) {
                stack[idx++] = '/';
            } else if (c == 1) {
                idx--;
            } else {
                idx -= 3;
                while (idx > 0 && stack[idx - 1] != '/') {
                    idx--;
                }
                if (idx == 0) {
                    idx++;
                }
            }
            c = 0;
        }
        if (idx != 1 && stack[idx - 1] == '/') {
            idx--;
        }
        return new String(stack, 0, idx);
    }

    /**
     * split+stringbuilder
     * @param path
     * @return
     */
    public String simplifyPath5(String path) {
        String[] split = path.split("\\/+");
        StringBuilder builder = new StringBuilder();
        int index = -1;
        for (int i = 1; i < split.length; i++) {
            if (split[i].equals("..")){
                if (index > -1){
                    builder.delete(builder.length() - split[index--].length() - 1, builder.length());
                }
            }else if (!split[i].equals(".")){
                builder.append("/");
                builder.append(split[i]);
                split[++index] = split[i];
            }
        }
        return builder.length() == 0? "/" : builder.toString();
    }

    /**
     * 民间-双指针
     * @param path
     * @return
     */
    public String simplifyPath6(String path) {
        String[] list = new String[path.length() >> 1];
        byte[] bytes = path.getBytes();
        int l = 0, r, i = 0;
        while(l < path.length()) {
            while(l < path.length() && bytes[l] == '/') {
                l++;
            }
            r = l;
            while(l < path.length() && bytes[l] != '/') {
                l++;
            }
            if(l == r) {
                break;
            }
            String s = path.substring(r, l);
            if("..".equals(s)) {
                if(i != 0) {
                    i--;
                }
            }else if (!".".equals(s)){
                list[i++] = s;
            }
        }
        StringBuilder builder = new StringBuilder();
        for(l = 0; l < i; l++) {
            builder.append("/");
            builder.append(list[l]);
        }
        return builder.length() == 0? "/" : builder.toString();
    }
}
